home *** CD-ROM | disk | FTP | other *** search
/ Libris Britannia 4 / science library(b).zip / science library(b) / CUGUK / PROG_TOO / C027B.ZIP / TOP / HEALTH.C < prev    next >
Text File  |  1990-03-30  |  4KB  |  175 lines
  1. /* Copyright (c) 1988 by Sozobon, Limited.  Author: Tony Andrews
  2.  *
  3.  * Permission is granted to anyone to use this software for any purpose
  4.  * on any computer system, and to redistribute it freely, with the
  5.  * following restrictions:
  6.  * 1) No charge may be made other than reasonable charges for reproduction.
  7.  * 2) Modified versions must be clearly marked as such.
  8.  * 3) The authors are not responsible for any harmful consequences
  9.  *    of using this software, even if they result from defects in it.
  10.  */
  11.  
  12. /*
  13.  * Routines for data flow analysis by block and function.
  14.  */
  15.  
  16. #include "top.h"
  17.  
  18. /*
  19.  * bprep() - perform initial analysis of individual blocks
  20.  */
  21. static    void
  22. bprep(bp)
  23. BLOCK    *bp;
  24. {
  25.     BLOCK    *cp;
  26.     INST    *ip;
  27.     int    ref, set;
  28.  
  29.     for (cp = bp; cp != NULL ;cp = cp->next) {
  30.         ref = set = 0;
  31.         for (ip = cp->first; ip != NULL ;ip = ip->next) {
  32.             ref |= (ip->rref = reg_ref(ip)) & ~set;
  33.             set |= (ip->rset = reg_set(ip));
  34.         }
  35.         cp->rref = ref;
  36.         cp->rset = set;
  37.     }
  38. }
  39.  
  40.  
  41. static    bool
  42. scan_ref(bp, reg)
  43. BLOCK    *bp;
  44. int    reg;
  45. {
  46.     INST    *ip;
  47.  
  48.     if (bp == NULL)
  49.         return FALSE;
  50.  
  51.     if (bp->rref & reg)
  52.         return TRUE;
  53.  
  54.     if (bp->rset & reg)
  55.         return FALSE;
  56.  
  57.     if (bp->flags & B_MARK)
  58.         return FALSE;
  59.  
  60.     if (bp->flags & B_RET)
  61.         return FALSE;
  62.  
  63.     bp->flags |= B_MARK;
  64.  
  65.     if (scan_ref(bp->bcond, reg))
  66.         return TRUE;
  67.  
  68.     if (scan_ref(bp->bfall, reg))
  69.         return TRUE;
  70.  
  71.     for (ip = bp->first; ip != NULL ;ip = ip->next) {
  72.         if (ip->opcode == DC && (ip->flags & LENL)) {
  73.             BLOCK    *db;
  74.  
  75.             if ((ip->src.astr != NULL) &&
  76.                 (db = getsym(ip->src.astr)) != NULL)
  77.                 if (scan_ref(db, reg))
  78.                     return TRUE;
  79.         }
  80.     }
  81.     return FALSE;
  82. }
  83.  
  84. /*
  85.  * is_live(bp, reg) - is 'reg' live at the end of block 'bp'
  86.  *
  87.  * Look ahead through the traversal graph to see what might happen to the
  88.  * given register. If we can find any reachable block that references 'reg'
  89.  * before setting it, the register is live. Scanning stops when the register
  90.  * is set, we loop back to the starting block, or the function returns.
  91.  */
  92. static    bool
  93. is_live(bp, reg)
  94. BLOCK    *bp;
  95. int    reg;
  96. {
  97.     INST    *ip;
  98.     BLOCK    *cp;
  99.  
  100.     /*
  101.      * Clear all the mark bits
  102.      */
  103.     for (cp = fhead; cp != NULL ;cp = cp->next)
  104.         cp->flags &= ~B_MARK;
  105.  
  106.     bp->flags |= B_MARK;
  107.  
  108.     if (scan_ref(bp->bfall, reg))
  109.         return TRUE;
  110.  
  111.     if (scan_ref(bp->bcond, reg))
  112.         return TRUE;
  113.  
  114.     for (ip = bp->first; ip != NULL ;ip = ip->next) {
  115.         if (ip->opcode == DC && (ip->flags & LENL)) {
  116.             BLOCK    *db;
  117.  
  118.             if ((ip->src.astr != NULL) &&
  119.                 (db = getsym(ip->src.astr)) != NULL)
  120.                 if (scan_ref(db, reg))
  121.                     return TRUE;
  122.         }
  123.     }
  124.     return FALSE;
  125. }
  126.  
  127. /*
  128.  * bflow() - live/dead analysis for a given block
  129.  *
  130.  * Work backward from the end of the block, checking the status of registers.
  131.  * To start with, figure out the state of each register as of the end of the
  132.  * block. Then work backward, checking registers only as necessary.
  133.  */
  134. static    void
  135. bflow(bp)
  136. BLOCK    *bp;
  137. {
  138.     INST    *ip;
  139.     int    live = 0;
  140.     int    reg;
  141.  
  142.     /*
  143.      * Figure out what's alive at the end of this block.
  144.      */
  145.     for (reg = FIRSTREG; reg <= LASTREG ;reg++) {
  146.         if (is_live(bp, RM(reg)))
  147.             live |= RM(reg);
  148.     }
  149.     /*
  150.      * Now work through the instructions in the block.
  151.      */
  152.     for (ip = bp->last; ip != NULL ;ip = ip->prev) {
  153.         ip->live = live;
  154.  
  155.         for (reg = FIRSTREG; reg <= LASTREG ;reg++) {
  156.             if (ip->rref & RM(reg))
  157.                 live |= RM(reg);
  158.             else if (ip->rset & RM(reg))
  159.                 live &= ~RM(reg);
  160.         }
  161.     }
  162. }
  163.  
  164. void
  165. rhealth(bp)
  166. BLOCK    *bp;
  167. {
  168.     register BLOCK    *cp;
  169.  
  170.     bprep(bp);
  171.  
  172.     for (cp = bp; cp != NULL ;cp = cp->next)
  173.         bflow(cp);
  174. }
  175.